\chapter{Вопрос №2}

Понятие $k$-сочетния с повторениями. Подсчет их числа с помощью принципа биекции. Формальное и комбинаторное доказательство рекуррентного соотношения. Доказательство тождества:
\[
	\sum_{i=0}^{k-1}\binom{n+k-i-1}{n} = \binom{n+k}{n+1}
\]
вывод его следствий.

\section{$k$-сочетние с повторениями}

$k$-сочетанием с повторениями из $n$ называется $k$-мультимножество над $n$-множеством. Число таких $k$-сочетний с повторениями обозначается:
\[
	\Binomrep{n}{k}
\]
читается сочетание из $n$ по $k$ с повторениями.

\section{Подсчет числа сочетаний с повторениями}
Произвольному $n$-множеству ставим в соответствие множество $$ \left\{1, 2, ... n\right\}$$. Рассмотрим $k$-мультимножество над этим множеством. Упорядочим все элементы мультимножества по неубыванию, тогда справедливо соотношение:
\[
	1 \le x_1 \le x_2 \le x_3 \le ... \le x_k \le n
\]
увеличим каждый $x_i$ на $i-1$ (это отображение биективно):
\[
	1 \le x_1 < x_2 < x_3 < ... <x_k \le n + k - 1
\]
получили $k$-сочетние без повторений из $n+k-1$, следовательно:
\begin{equation}
	\Binomrep{n}{k} = \binom{n+k-1}{k}
\end{equation}
\section{Рекуррентное соотношение}
Разобьем все $k$-сочетания с повторениями из $n$ на два непересекающихся класса:
\begin{enumerate}
\item В первый класс входят только мультимножества в которые элемент $n$ не входит. Число таких мультимножеств определяется соотношением $$ \Binomrep{n-1}{k} $$.

\item Во второй класс входят только мультимножества в которые элемент $n$ входит как минимум один раз. Число таких мультимножеств определяется соотношением $$ \Binomrep{n}{k-1} $$.
\end{enumerate}
В итоге:
\begin{equation}
\Binomrep{n}{k} = \Binomrep{n-1}{k} + \Binomrep{n}{k-1}
\end{equation}

Доказать его не комбинаторно можно из связи с биномиальными коэффициентами:
\[
	\begin{split}
		& \Binomrep{n}{k} = \Binomrep{n-1}{k} + \Binomrep{n}{k-1} \Leftrightarrow \\
		& \binom{n+k-1}{k} = \binom{n+k-2}{k} + \binom{n+k-2}{k-1}
	\end{split}
\]

\section{Специальное тождество}
\[
	\Binomrep{n+1}{k} = \binom{n+k}{k} = \binom{n+k}{n}
\]
с другой стороны, если разбить все $k$-мультимножества над $\left(n+1\right)$ множеством на блоки $X_i$ таким образом, что в $X_i$ входят только мультимножества в которых кратность некоторого элемента $\#x_1 = i$.

Мощность каждого такого блока определяется соотношением:
\[
	\Binomrep{n+1-1}{k-i} = \binom{n+k-i-1}{k-i} = \binom{n+k-i-1}{n-1}
\]
следовательно:
\begin{equation}
	\binom{n+k}{n} = \sum_{i=0}^k\binom{n+k-i-1}{n-1}
\end{equation}
сделаем замену:
\[
	\begin{split}
		& \tilde n = n-1, n = \tilde n+1\\
		& \tilde k = k+1, k = \tilde k-1
	\end{split}
\]
тогда:
\begin{equation}
	\binom{\tilde n+\tilde k}{\tilde n+1} = \sum_{i=0}^{\tilde k - 1}\binom{\tilde n+\tilde k-i-1}{\tilde n}
\end{equation}
